Mobile ad hoc networks (MANETs) are an important technology for mission critical military communications. They enable communication between a group of nodes to form a network in absence of infrastructure components such as base stations and power sources. The nodes themselves are often portable radios in soldier's backpacks, in combat vehicles, etc where size, weight, energy efficiency, and the ability to maintain reliable communication are key constraints. The applications that use these networks often require continuous “group communication”. For example, soldiers in a team may be continuously exchanging voice messages, or a set of battlefield tanks may be exchanging shared situation awareness information such as their locations or their targets. Furthermore, even in the case of unicast routing in mobile ad hoc networks, flooding or broadcast is frequently used to discover unicast routes between a source and a destination. Thus, efficient support for group broadcast semantics, where data is sent to all or most of the nodes, is critical for these networks.
To date, research on efficient broadcast support in mobile ad hoc networks has proceeded along two main approaches: probabilistic and deterministic. Probabilistic or gossiping-based approaches require each node to rebroadcast the packet to its neighbors with a given forwarding probability. The key challenge with these approaches is to tune the forwarding probability: keeping it as low as possible for maximum efficiency while maintaining it high enough, so that all the nodes are able to receive the broadcast packets. Deterministic approaches on the other hand predetermine and select the neighboring nodes that forward the broadcast packet. If the complete topology is used (feasible for static ad hoc networks), a good approximation algorithm, such as that described by K. M. Alzoubi, P. J. Wan, and O. Frieder, in “New distributed algorithm for connected dominating set in wireless ad hoc networks,” in HICSS, 2002, for constructing a small connected dominating set-based based approach will yield very few transmissions to reach all nodes; otherwise, pruning-based solutions based on one or two hop topology information have to be adopted.
Separately, network coding, i.e. allowing intermediate nodes to combine packets before forwarding, has been shown to significantly improve transmission efficiency in wired networks. See for example, R. Ahlswede, N. Cai, S. Li, and R. Yeung, “Network information flow,” IEEE Transactions on Information Theory, 2000. Recently, network coding has been adapted to support unicast and multicast applications in wireless networks. In “A network coding approach to energy efficient broadcasting: from theory to practice,” by C. Fragouli, J. Widmer, and J.-Y. L. Boudec in IEEE Infocom, April 2006, network coding is shown to be adapted to a probabilistic approach for supporting broadcast in mobile ad hoc networks. However, this approach has several drawbacks. As mentioned earlier, fine-tuning the forwarding probability in probabilistic approaches is a difficult problem—in order to ensure that most nodes receive the broadcast; one typically chooses a higher forwarding probability that results in inefficiencies compared to a deterministic approach. Also, the approach described by Fragouli et al. has to group packets transmitted from various sources into globally unique sets called generations, where solving in a distributed manner is a difficult problem and limits coding gains. Furthermore, the use of a globally unique set of coded packets implies that the decoding delay can be large, since enough information must be received from the various sources before a generation can be decoded at a node.
The problem of broadcast support in mobile ad hoc networks has been extensively studied. The high overhead of using naive flooding to support broadcast was highlighted in an article by S. Ni, Y. Tseng, Y. Chen, and J. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proceedings of the 5th annual international conference on Mobile computing and networking, pp. 151-162, 1999. Since then, researchers have adopted either deterministic or probabilistic approaches to support broadcast efficiently.
Under deterministic approaches, if complete topology information is known, a connected dominating set-based approach will yield optimal results. However, for mobile ad hoc networks, the availability of complete topology information, that remains current for reasonable durations, is unrealistic. Thus, algorithms that rely only on local topology information were developed. In H. Lim and C. Kim, “Flooding in wireless ad hoc networks,” Computer Communications Journal, vol. 24, no. 3-4, pp. 353-363, 2001, the authors propose two algorithms called self pruning and dominant pruning that rely on 1-hop and 2-hop neighborhood information respectively, to reduce redundant broadcasts as compared to a flooding based approach. In W. Lou and J. Wu, “On reducing broadcast redundancy in ad hoc wireless networks,” IEEE Transactions on Mobile Computing, vol. 1, no. 2, pp. 111-123, 2002, the authors propose total dominant pruning and partial dominant pruning (PDP) that rely on 3-hop and 2-hop neighborhood information respectively, to improve on the proposals by Lim and Kim above.
Recently, there has been interest in the use of network coding to improve transmission efficiency in networks. In the article by R. Ahlswede, N. Cai, S. Li, and R. Yeung, “Network information flow,” IEEE Transactions on Information Theory, 2000. The article showed networks that allow intermediate nodes to combine information before forwarding results in significant throughput gains over networks with intermediate nodes that only forward information. Support for multicast and broadcast in wireless networks with network coding can also be addressed either using deterministic or probabilistic approaches. Under probabilistic approaches, authors in Fragouli et al. show that practical coding-based probabilistic schemes significantly outperform non-coding based probabilistic schemes. Under deterministic approaches, articles by D. et al., “Achieving minimum-cost multicast: A decentralized approach based on network coding,” in IEEE Infocom, March 2005 and Y. Wu, P. Chou, and S.-Y. Kung, “Minimum-energy multicast in mobile ad hoc networks using network coding,” IEEE Transactions on communications, vol. 53, no. 11, pp. 1906-1918, 2005 study theoretical solutions based on solving linear programs that assume knowledge of the entire network topology and show significant gains in terms of efficiency and computational overhead over approaches that do not use network coding. Practical and deterministic coding-based schemes for support of unicast traffic in wireless networks have been studied in an article by S. Katti, D. Katabi, W. Hu, H. Rahul, and M. Medard, “The importance of being opportunistic: Practical network coding for wireless environments,” in ACM Sigcomm, September 2006. However, none of the prior art references set forth a practical and deterministic coding-based schemes that use only local topology information for efficient support of broadcasts. Accordingly, there is a need for such a system.